package com.yww.datastructure.priorityqueue;

import com.yww.datastructure.queue.Queue;

import java.util.Arrays;
import java.util.Iterator;

/**
 * @author yww
 * @description 无序数组实现的优先级队列（出队使用一次选择排序）
 * @since 2024/2/6 9:33
 */
public final class PriorityQueue1<E extends Priority> implements Queue<E> {

    private final Priority[] array;
    private int size;

    public PriorityQueue1(int capacity) {
        this.array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[size++] = value;
        return true;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax(array, size);   // 找到优先级最大的元素索引
        Priority val = array[max];

        remove(max, size, array); // 数组元素往下移动
        size--;
        return (E) val;
    }

    private static void remove(int index, int size, Priority[] array) {
        if (index < size - 1) {
            System.arraycopy(array, index + 1, array, index, size - 1 - index);
        }
        array[size - 1] = null; // help gc
    }

    private static int selectMax(Priority[] array, int size) {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax(array, size);   // 找到优先级最大的元素索引
        Priority val = array[max];
        return (E) val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int tempSize = size;
            final Priority[] temp = Arrays.copyOf(array, size);

            @Override
            public boolean hasNext() {
                return tempSize > 0;
            }

            @Override
            public E next() {
                int max = selectMax(temp, tempSize);
                Priority priority = temp[max];

                PriorityQueue1.remove(max, tempSize, temp);
                tempSize--;
                return (E) priority;
            }
        };
    }
}
